package com.basic;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class OpenLock {

	public static void main(String[] args) {
		String[] s = new String[]{"0201","0101","0102","1212","2002"};
		String target = "0202";
		int step = BFS(s,target);
		System.out.println(step);
	}
	
	public static int BFS(String[] deadends, String target) {
		Set<String> deads = new HashSet();
		for(String el:deadends) deads.add(el);
		
		Queue<String> queue = new LinkedList<>();
		Set<String> vivisted = new HashSet();
		
		int step = 0;
		queue.offer("0000");
		vivisted.add("0000");
		while(!queue.isEmpty()) {
			int n = queue.size();
			for (int j = 0; j < n; j++) {
				String temp = queue.poll();
				if(deads.contains(temp))
					continue;
				if(temp.equals(target))
					return step;
				for(int i = 0;i < 4;i++) {
					String temp1 = plusOne(temp,i);
					if(!vivisted.contains(temp1))
					{
						queue.offer(temp1);
						vivisted.add(temp1);
					}
				}
				for(int i = 0;i < 4;i++) {
					String temp1 = downOne(temp,i);
					if(!vivisted.contains(temp1))
					{
						queue.offer(temp1);
						vivisted.add(temp1);
					}
				}
			}
			step++;	
		}
		return -1;
	}
	public static String plusOne(String cur,int j) {
		char[] temp = cur.toCharArray();
		if(temp[j] == '9')
			temp[j] = '0';
		else
			temp[j] += 1;
		return new String(temp);
	}
	public static String downOne(String cur,int j) {
		char[] temp = cur.toCharArray();
		if(temp[j] == '0')
			temp[j] = '9';
		else
			temp[j] -= 1;
		return new String(temp);
	}
}
